//
// test.go
// Copyright (C) 2019 crane <crane@his-pc>
//
// Distributed under terms of the MIT license.
//

package main

import (
	"fmt"
	"math"
)

func proceed_head(cur_array []int, head_idxs []int, i int, cur_idx int, head_max *int) bool {
	is_match := false

	for ; cur_idx < len(cur_array); cur_idx++ {
		v := cur_array[cur_idx]

		if v == *head_max {
			// match_cnt += 1
			is_match = true
			break
		} else if v > *head_max {
			*head_max = v

			break
		}
	}
	head_idxs[i] = cur_idx

	return is_match
}

// 使用归并方式, 取union, 所有union都match时的第一个值即为ret
func find(mat [][]int) int {

	group_len := len(mat)

	// 记录每个一维数组即将访问到的index
	head_idxs := make([]int, group_len)

	head_max := math.MinInt32 // 初始化为int 最小值

	for {
		match_cnt := 0

		for i := 0; i < group_len; i++ {
			cur_idx := head_idxs[i]
			cur_array := mat[i]

			if cur_idx >= len(cur_array) {
				return -1
			}

			cur_head := cur_array[cur_idx]

			if cur_head == head_max {
				fmt.Println("match", i)
				match_cnt += 1
			} else if cur_head > head_max {
				// match_cnt 不变或者清零, 总之这次循环结束match_cnt和二维数组长度不等
				head_max = cur_head
			} else {
				// 当前数组头部比head_max 小, 头部index 一直前进
				is_match := proceed_head(cur_array, head_idxs, i, cur_idx, &head_max)
				if is_match {
					match_cnt += 1
				}
			}
		}

		fmt.Println("match_cnt", match_cnt, "\n")

		if match_cnt == len(mat) {
			return head_max
		}

	}
}

func main() {
	fmt.Println("start main")
	mat := [][]int{
		[]int{1, 3, 4, 5},
		[]int{2, 3, 5},
		[]int{3, 5, 6},
		[]int{4, 5, 6},
	}

	ret := find(mat)
	fmt.Println(ret)
}
